class NP-hard
NP-hard
#complexity_theory
#complexity_theory
Definition
Define language as NP-hard if for every NP. (polynomial-time reduction from to )
(see NP, also note that means polynomial-time reduction)
References
- S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 42.